package offer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhanBo
 * @date 2020/5/26
 */
public class Solution39 {

    public static void main(String[] args) {
        int [] array = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        System.out.println(majorityElement(array));

    }

    /**
     * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     *
     * 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
     * 输出: 2
     *
     * 1 <= 数组长度 <= 50000
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>(16);
        for (int n :nums){
            if (map.containsKey(n)){
                map.put(n,map.get(n)+1);
            }else {
                map.put(n,1);
            }
        }
        for (int result :nums){
            if (map.get(result)>(nums.length/2)){
                return result;
            }
        }
        return -1;
    }


    /**摩尔投票法：
     *      1、票数和： 由于众数出现的次数超过数组长度的一半；若记 众数 的票数为 +1+1 ，非众数 的票数为 -1−1 ，则一定有所有数字的 票数和 > 0>0 。
     *      2、票数正负抵消： 设数组 nums 中的众数为 xx ，数组长度为 nn 。若 nums 的前 aa 个数字的 票数和 = 0=0 ，则 数组后 (n-a)(n−a) 个数字的
     *      票数和一定仍 >0>0 （即后 (n-a)(n−a) 个数字的 众数仍为 xx ）。
     *算法原理：
     * 1、为构建正负抵消，假设数组首个元素 n1为众数，遍历统计票数，当发生正负抵消时，剩余数组的众数一定不变 ，这是因为（设真正的众数为 xx ）：
     *      当 n1 = x： 抵消的所有数字中，有一半是众数 xx 。
     *      当 n1 ≠ X：抵消的所有数字中，少于或等于一半是众数 xx 。
     *2、利用此特性，每轮假设都可以 缩小剩余数组区间 。当遍历完成时，最后一轮假设的数字即为众数（由于众数超过一半，最后一轮的票数和必为正数）。
     *
     * 算法流程:
     * 1、初始化： 票数统计 votes = 0votes=0 ， 众数 xx；
     * 2、循环抵消： 遍历数组 nums 中的每个数字 numnum ；
     *      当 票数 votesvotes 等于 00 ，则假设 当前数字 numnum 为 众数 xx ；
     *      当 num = xnum=x 时，票数 votesvotes 自增 11 ；否则，票数 votesvotes 自减 11 。
     * 3、返回值： 返回 众数 xx 即可。
     * @param nums
     * @return
     */
    public static int majorityElement2(int[] nums) {
        int x = 0, votes = 0;
        for(int num : nums){
            if(votes == 0) {
                x = num;
            }
            votes += num == x ? 1 : -1;
        }
        return x;
    }
    /**
     *由于题目明确给定 给定的数组总是存在多数元素 ，因此本题不用考虑 数组中不存在众数 的情况。
     *若考虑，则需要加入一个 “验证环节” ，遍历数组 nums 统计 xx 的数量。
     *      若 xx 的数量超过数组长度一半，则返回 xx ；
     *      否则，返回 00 （这里根据不同题目的要求而定）。
     *时间复杂度仍为 O(N)O(N) ，空间复杂度仍为 O(1)O(1) 。
     * @param nums
     * @return
     */
    public static int majorityElement3(int[] nums) {
        int x = 0, votes = 0, count = 0;
        for(int num : nums){
            if(votes == 0) {
                x = num;
            }
            votes += num == x ? 1 : -1;
        }
        // 验证 x 是否为众数
        for(int num : nums) {
            if(num == x) {
                count++;
            }
        }
        // 当无众数时返回 0
        return count > nums.length / 2 ? x : 0;
    }
}
